package com.zp.self.module.level_4_算法练习.数据结构.二叉树;

import java.util.Stack;

/**
 * @author  ZengPeng
 **/
public class 力扣_110_平衡二叉树 {
    public static void main(String[] args) {
        TreeNode root = TreeNode.initRoot();
        System.out.println( new 力扣_110_平衡二叉树().isBalanced(root));
        System.out.println( new 力扣_110_平衡二叉树().isBalanced(null));
    }

    /**
     * 题目：
     * 给定一个二叉树，判断它是否是高度平衡的二叉树。
     * 本题中，一棵高度平衡二叉树定义为：
     * 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
     *
     * 分析：
     *  递归法，求每个节点的 左右子树最大深度  ，相减的绝对值<=1
     *  注意点：是所有节点都要满足，并不是只要根节点满足
     *  优化：弹栈？ 记录？ --- 去除栈 ，直接递归判断  -- 递归返回-1  标识不平衡.....
     *
     * 边界值注意：
     *  1.root==null
     **/
    public boolean isBalanced(TreeNode root) {
        if(root ==null) return true;
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        while (!stack.isEmpty()){
            TreeNode pop = stack.pop();
            if(Math.abs(recursive(pop.left)-recursive(pop.right))>1) return false;
            if(pop.left!=null)
                stack.push(pop.left);
            if(pop.right!=null)
                stack.push(pop.right);
        }
        return  true;
    }

    private  int recursive(TreeNode root){
        if(root==null) return 0;
        return  Math.max(recursive(root.left),recursive(root.right))+1;
    }
}
